1. Technical Field
The invention relates generally to semiconductor manufacturing, and more particularly, to a method, system and program product for planning production for complementary demands.
2. Background Art
One problem faced in all manufacturing industries is the allocation of material and capacity assets to meet end customer demand. Production lead times necessitate the advance planning of production starts, interplant shipments, and material substitutions throughout the supply chain so that these decisions are coordinated with the end customers' demand for any of a wide range of finished products (e.g., typically on the order of thousands in semiconductor manufacturing). Such advance planning depends upon the availability of finite resources which include: finished goods inventory, work in process (WIP) inventory at various stages of the manufacturing system, and work-center capacity. Often, there are alternative possibilities for satisfying the demand. Products may be built at alternative locations and within a location there may be choices as to which materials or capacity to use to build the product. The product may be built directly or acquired through material substitution or purchase. When limited resources prevent the satisfaction of all demands, decisions need to be made as to which demand to satisfy and how to satisfy it. This resource allocation problem is often addressed through linear programming or other advanced planning and scheduling methods.
A conventional production planning linear program “LP” is shown below. (U.S. Pat. No. 5,971,585 describes an LP also). This LP makes decisions including: production starts, material substitutions, and shipments planned to customers, between manufacturing and distribution locations, and from vendor suppliers. An LP is composed of an objective function that defines a measure of the quality of a given solution, and a set of linear constraints. The types of equations used in production planning models are well known to those practiced in the art and include:
(1) Material Balance Constraints, which ensure conservation of material flow through the network of stocking points comprising the supply chain.
(2) Capacity Constraints, which ensure that the capacity available for manufacturing activities is not exceeded.
(3) Backorder Conservation Constraints, which balance the quantity of a given part backordered in a given planning period with the quantity backordered in the previous planning period and the net of new demand and new shipments.
(4) Sourcing Constraints, which define target ranges (minimum and maximum) of shipments that should be made from a particular manufacturing or vendor location in the supply chain.
A conventional LP formulation is provided below, i.e., definition of subscripts, definition of objective function coefficients, definition of constants, definition of decision variables, and LP formulation or equations.
Definition of Subscripts:
    j: time period    m: material (part number)    a: plant location within the enterprise    n: material being substituted    z: group (which represents a family or collection of part numbers)    e: process (a method of purchasing or manufacturing a material at a plant)    v: receiving plant location    k: demand center (i.e., customer location) (Note: the set of customer locations is mutually exclusive from the set of plant locations)    q: demand class which indicates relative priority    w: resource capacity which could be a machine, labor hour, or other constraint    u: represents a consumer location which refers to an internal plant, external demand center, or to a generic indicator meaning any plant/or demand centerDefinition of Objective Function Coefficients:    PRCjmae: cost of releasing one piece of part m during period j at plant a using process e    SUBCjmna: substitution cost per piece of part number n which is being substituted by part number m during period j at plant a    TCjmav: transportation cost per piece of part number m leaving plant a during period j which are destined for plant v    INVCjma: inventory cost of holding one piece of part number m at the end of period j at a particular plant a    DMAXCjzau: cost per piece of exceeding the maximum amount of shipments of group z parts from plant a to consuming location(s) u during period j    DMINCjzau: cost per piece of falling short of the minimum amount of shipments specified for group z parts from plant a to consuming location(s) u during period j    BOCjmkq: backorder cost of one piece of part m at the end of period j for class q demand at customer location kDefinition of Constants:    DEMANDjmkq: demand requested during time period j for part number m at customer location k for demand class q    RECEIPTjma: quantity of projected wip and purchase order receipts for part number m expected to be received at plant a during time period j    CAPACITYjaw: capacity of resource w available at plant a during period j to support production starts    CAPREQjmaew: capacity of resource w required for part number m at plant a for process e during period j    QTYPERjmaen: quantity of component m needed per part number n during period j at plant a using process e    YIELDjmae: output of part number m per piece released or started at plant a during time period j using process e    SUBQTYjmna: quantity of part number m required to substitute for one piece of part number n at plant a during time period j    MAXPCTjzau: maximum percentage of total shipments of group z (collection of parts) leaving supplier a during period j to support consumption at consuming location(s) u    MINPCTjzau: minimum percentage of total shipments of group z (collection of parts) leaving supplier a during period j to support consumption at consuming location(s) u    CTjmae: cycle time. The number of periods between the release and completion of part m jobs for releases made using process e at plant a during time period j    TTmav: transport time for part number m from plant a to plant vDefinition of LP Decision Variables:    Ijma: inventory at the end of period j for part number m at a particular plant a    Pjmae: production starts of part m during period j at plant a using process e    Ljmna: quantity of part number n which is being substituted by part number m during period j at plant a    Tjmav: internal shipments of part number m leaving plant a during period j which are destined for plant v    Fjmakq: shipments of part number m leaving plant a during period j and satisfying class q demand at external customer k    Bjmkq: back orders of part m at the end of period j for class q demand at customer location k    Hjzu: total shipments of group z (z is a “collection” of parts) leaving suppliers during period j to support consumption at consuming location(s) u    Sjzau: amount by which total shipments of parts in z from plant a to consuming location(s) u during period j exceeds the maximum amount specified as desired in the sourcing rules    Gjzau: amount by which total shipments of group z parts from plant a to consuming location(s) u during period j falls short of the minimum amount specified as desired in the sourcing rulesLP Equations or Formulation:
The following minimizes the objective function subject to the constraints shown below.
Objective Function:
Minimize:
            ∑      j        ⁢                  ∑        m            ⁢                        ∑          a                ⁢                              ∑            e                    ⁢                                    PRC              jmae                        ⁢                          P              jmae                                            +            ∑      j        ⁢                  ∑        m            ⁢                        ∑          n                ⁢                              ∑            a                    ⁢                                    SUBC              jmna                        ⁢                          L              jmna                                            +            ∑      j        ⁢                  ∑        m            ⁢                        ∑          a                ⁢                              ∑            v                    ⁢                      T            ⁢                                                  ⁢                          C              jmav                        ⁢                          T              jmav                                            +            ∑      j        ⁢                  ∑        m            ⁢                        ∑          a                ⁢                              INVC            jma                    ⁢                      I            jma                                +            ∑      j        ⁢                  ∑        z            ⁢                        ∑          a                ⁢                              ∑            u                    ⁢                                    DMAXC              jzau                        ⁢                          S              jzau                                            +            ∑      j        ⁢                  ∑        z            ⁢                        ∑          a                ⁢                              ∑            u                    ⁢                                    DMINC              jzau                        ⁢                          G              jzau                                            +            ∑      j        ⁢                  ∑        m            ⁢                        ∑          k                ⁢                              ∑            q                    ⁢                                    BOC              jmkq                        ⁢                          B              jmkq                                          Subject to:a) Sourcing Constraints:
            H      jzu        =                  ∑                  m          ɛz                    ⁢                        ∑          a                ⁢                  (                                    T              jmau                        +                                          ∑                q                            ⁢                              F                jmauq                                              )                                                  ∑                      m            ɛz                          ⁢                  (                                    T              jmau                        +                                          ∑                q                            ⁢                              F                jmauq                                              )                    -              S        jzau              ≤                  MAXPCT        jzau            ⁢              H        jzu                                          ∑                      m            ɛz                          ⁢                  (                                    T              jmau                        +                                          ∑                q                            ⁢                              F                jmauq                                              )                    -              G        jzau              ≤                  MINPCT        jzau            ⁢              H        jzu            b) Capacity Constraints:
            ∑      m        ⁢                  ∑        e            ⁢                        CAPREQ          jmaew                ⁢                  P          jmae                      ≤      CAPACITY    jaw  c) Backorder Constraints:
      B    jmkq    =            B                        (                      j            -            1                    )                ⁢        mkq              +          DEMAND      jmkq        -                  ∑        a            ⁢              F        jmakq            d) Material Balance Constraints:
      I    jma    =            I                        (                      j            -            1                    )                ⁢        ma              +          RECEIPT      jma        +                  ∑                  x…s…t                                    x              +                              CT                xmae                                      =            j                              ⁢                        ∑          e                ⁢                              YIELD            xmae                    *                      P            xmae                                +                  ∑        n            ⁢              L        jmna              +                  ∑                  .                                    xs              .              t                                                      x                +                                  TT                  mav                                            =              j                                          ⁢                        ∑          v                ⁢                  T          xmva                      -                  ∑        n            ⁢                        SUBQTY          jmna                *                  L          jmna                      -                  ∑        v            ⁢              T        jmav              -                  ∑        k            ⁢                        ∑          q                ⁢                  F          jmakq                      -                  ∑                              n            ⁢                                                  ⁢                          st              .              m                                            is            ⁢                                                  ⁢            a            ⁢                                                  ⁢                          component                              of                ⁢                                                                  ⁢                n                                                        ⁢                        ∑          e                ⁢                              QTYPER                          jmaen              ⁢                                                                            ⁢                      P            jnae                              e) Non-Negativity Constraints:
All Xi,j . . . ≧0, where X is a generic decision variable and i, j, etc. represent generic subscripts.
Referring to FIG. 1, linear programming applications typically include the transformation of input files (inputs) 10 into output files (outputs) 18 through a pre-processor 12, a solver 14, and a post-processor 16. Pre-processor 12 transforms the raw input files 10 into a form useable by the linear programming solver 14. Solver 14 determines an optimal raw output solution, which is transformed by post-processor 16 into a format acceptable for usage.
One problem with conventional linear programming applications and other advanced planning and scheduling (APS) methods is that they do not handle complementary demands. That is, demands that collaboratively influence the production of elements of a supply chain wherein no single (complementary) demand directly influences production of an entire chain.